regret bound

Definition (regret)

Choose $\mathbf{x}^{(1)},…,\mathbf{x}^{(T)}$ so that:

\sum_{i=1}^T f_i (\mathbf{x}^{(i)}) \leq \left[\min_\mathbf{x} \sum_{i=1}^T f_i (\mathbf{x})\right] + \epsilon

Here $\epsilon$ is called the regret of our solution sequence $\mathbf{x}^{(1)},…,\mathbf{x}^{(T)}$ . Regret compares to the best fixed solution in hindsight.

We typically observe $\epsilon$ to be growing sublinearly in $T$ .

Notes

Either $f_1, . . . , f_T$ are similar or changing slowly, so we can learn predict $f_i$ from earlier functions.
Or $f_1, . . . , f_T$ are very different, in which case $\min_x \sum_{i=1}^T f_i(x)$ is large, so regret bound is easy to achieve.
Or we live somewhere in the middle.

Definition (regret)

Notes

See also